(1) Field of the Invention
The present invention relates to a signal processing apparatus and more particularly to a circuit realization of a complicated data sorting or scrambling scheme which is necessary prior to executing various fast Fourier transform (FFT) computations.
(2) Description of the Prior Art
It is well known that the fast Fourier transform is an algorithm which reduces the number of computation steps from N.sup.2 to NlogN where N is the size of the transform. This saving in computations amounts to a factor of 200 reduction for the size transforms typically used in signal processing systems. A significant difficulty in using the FFT however is that the selection order in which the data samples are accessed is complicated.
A radix-2, decimation-in-time algorithm can be used to describe the data ordering problem. A key step in the derivation is to sort a naturally ordered input sequence of N points into a subsequence which contains the N/2 even numbered samples and into another subsequence which contains the N/2 odd number samples. Next, the subsequence of even numbered samples is itself sorted into an even group and an odd group. Each of these resulting subsequences include N/4 points each. Similarly the odd samples from the first sort are also sorted into an even and an odd group. The sorting process of breaking each group into a new even group and a new odd group continues until there are only two samples left in each group, and they are already sorted into even and odd because there are only two samples left. Once the original data set is reordered in the above fashion, the computation of the FFT can proceed.
The problem becomes one of determining where each data sample in the original sequence ends up in the sorted sequence. In the past, this reordering or pre-scrambling of data has been accomplished by software, firmware and hardware methods.
The software implementation requires coding the sorting procedure in a language such as FORTRAN. Such sorting is time consuming however because nested loops with variable indices are needed to keep track of which subsequence is being sorted together with its length.
The firmware procedure consists of pre-determining where each data point ends up after sorting and then storing the appropriate address in a read only memory (ROM). The ROM is then accessed while executing the FFT computation to determine the location of the appropriate data sample. However, this look-up-table scheme requires a unique ROM for each different length FFT or different radix FFT to be computed.
The hardware approach to re-ordering the data consists of a scheme known as "bit fiddling". The binary address of a naturally ordered data sample is put in a register and each of the bits are interchanged about the center bit of the register. Usually this bit interchange is accomplished by hardwiring the bits to different positions in the "fiddle" register. The problem associated with this hardware approach is that the bits are always interchanged about the center bit of the register. Thus a different size register is required for each size of FFT encounterd and, the interchange is only applicable to radix-2 FFTs.